package leetcode;


public class Code34 {
    public static void main(String[] args) {
       int[] i= new Code34().searchRange(new int[]{0,0,0,0,1,2,3,3,4,5,6,6,7,8,8,8,9,9,10,10,11,11},0);
        System.out.println(i[0]+" "+i[1]);
    }
    public int[] searchRange(int[] nums, int target) {
        return find(nums,0,nums.length-1,target);
    }

    public int[] find(int[] nums,int start,int end ,int target){
        if(start>end){
            return new int[]{-1,-1};
        }
        int index = nums[(start+end)/2];
        if(index>target){
            return find(nums,start,(start+end)/2-1,target);
        }else if (index < target){
            return find(nums,(start+end)/2+1,end,target);
        }else{
            int[] items = new int[2];
            int left=findIndex(nums,start,(start+end)/2-1,target,true);
            int right = findIndex(nums,(start+end)/2+1,end,target,false);
            items[0]=left==-1?(start+end)/2:left;
            items[1]=right==-1?(start+end)/2:right;
            return items;
        }
    }

    private int findIndex(int[] nums, int start, int end, int target,boolean left) {
        if(start>end){
            return -1;
        }
        int index = nums[(start+end)/2];
        if(index>target){
            return findIndex(nums,start,(start+end)/2-1,target,left);
        }else if (index<target){
            return findIndex(nums,(start+end)/2+1,end,target,left);
        }else{
            int other=-1;
            if(left){
                other = findIndex(nums,start,(start+end)/2-1,target,left);
            }else{
                other = findIndex(nums,(start+end)/2+1,end,target,left);
            }
            return other==-1?(start+end)/2:other;
        }
    }
}
